{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Word in Dictionary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #array #hash-table #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #数组 #哈希表 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestWord"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #词典中最长的单词"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出一个字符串数组&nbsp;<code>words</code> 组成的一本英语词典。返回&nbsp;<code>words</code> 中最长的一个单词，该单词是由&nbsp;<code>words</code>&nbsp;词典中其他单词逐步添加一个字母组成。</p>\n",
    "\n",
    "<p>若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"w\",\"wo\",\"wor\",\"worl\", \"world\"]\n",
    "<strong>输出：</strong>\"world\"\n",
    "<strong>解释：</strong> 单词\"world\"可由\"w\", \"wo\", \"wor\", 和 \"worl\"逐步添加一个字母组成。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"a\", \"banana\", \"app\", \"appl\", \"ap\", \"apply\", \"apple\"]\n",
    "<strong>输出：</strong>\"apple\"\n",
    "<strong>解释：</strong>\"apply\" 和 \"apple\" 都能由词典中的单词组成。但是 \"apple\" 的字典序小于 \"apply\" \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 30</code></li>\n",
    "\t<li>所有输入的字符串&nbsp;<code>words[i]</code>&nbsp;都只包含小写字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-word-in-dictionary](https://leetcode.cn/problems/longest-word-in-dictionary/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-word-in-dictionary](https://leetcode.cn/problems/longest-word-in-dictionary/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"w\",\"wo\",\"wor\",\"worl\",\"world\"]', '[\"a\",\"banana\",\"app\",\"appl\",\"ap\",\"apply\",\"apple\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        my_set = set()\n",
    "        target_word = \"\"\n",
    "        for word in words:\n",
    "            my_set.add(word)\n",
    "        for i in range(len(words)):\n",
    "            cur_word = words[i][:-1]\n",
    "            is_target = True\n",
    "            while cur_word != \"\":\n",
    "                if cur_word not in my_set:\n",
    "                    is_target = False\n",
    "                    break\n",
    "                cur_word = cur_word[:-1]\n",
    "            if is_target:\n",
    "                if len(words[i]) > len(target_word) or (len(words[i]) == len(target_word) and target_word > words[i]):\n",
    "                    target_word = words[i]\n",
    "        return target_word"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words.sort()\n",
    "        record , res = set() , \"\"\n",
    "        for word in words:\n",
    "            if word[:-1] in record or word[:-1] == \"\":\n",
    "                if len(word) > len(res): res = word\n",
    "                record.add(word)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        res = \"\"\n",
    "        wordset = set(words)\n",
    "        for word in words:\n",
    "            if len(word) > len(res) or (len(word) == len(res) and word < res):\n",
    "                if all(word[:k] in wordset for k in range(1, len(word))):\n",
    "                    res = word\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestWord(self, words: List[str]) -> str:\r\n",
    "        words.sort()\r\n",
    "        s = set([''])\r\n",
    "        ans = ''\r\n",
    "        for v in words:\r\n",
    "            n = len(v)\r\n",
    "            if v[:n - 1] in s:\r\n",
    "                if n > len(ans):\r\n",
    "                    ans = v\r\n",
    "                s.add(v)\r\n",
    "        return(ans)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words.sort(key = (lambda x: (len(x), x)))\n",
    "        s = set([''])\n",
    "        ans = ''\n",
    "        for w in words:\n",
    "            if w[:-1] in s:\n",
    "                s.add(w)\n",
    "                if len(w) > len(ans):\n",
    "                    ans = w\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        if words is None or len(words) == 0:\n",
    "            return ''\n",
    "        ans = ''\n",
    "        ss = set(words)\n",
    "        for word in words:\n",
    "            # 判断word是否符合长度\n",
    "            if len(word) > len(ans) or (len(word) == len(ans) and word < ans):\n",
    "                for i in range(1,len(word)+1):\n",
    "                    if word[:i] not in ss:\n",
    "                        break\n",
    "                else:\n",
    "                    ans = word\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words.sort(key=lambda x: (-len(x), x), reverse=True)\n",
    "        longest = \"\"\n",
    "        candidates = {\"\"}\n",
    "        for word in words:\n",
    "            if word[:-1] in candidates:\n",
    "                longest = word\n",
    "                candidates.add(word)\n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        if words is None:\n",
    "            return ''\n",
    "        words.sort(key=lambda word:(-len(word),word),reverse=True)\n",
    "        longest = ''\n",
    "        mp = {''}\n",
    "        for word in words:\n",
    "            if word[:-1] in mp:\n",
    "                mp.add(word)\n",
    "                longest = word\n",
    "        return longest\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words.sort()\n",
    "        s,res = set(['']),''\n",
    "        for i in words:\n",
    "            if i[:-1] in s:\n",
    "                s.add(i)\n",
    "                if len(i) > len(res):\n",
    "                    res = i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words.sort(key=lambda x: len(x))\n",
    "        hasmap = {}\n",
    "        max_len = 1\n",
    "        for word in words:\n",
    "            n = len(word)\n",
    "            if n == 1:\n",
    "                hasmap[word] = 1\n",
    "            else:\n",
    "                if word[:n-1] in hasmap:\n",
    "                    hasmap[word] = hasmap[word[:n-1]] + 1\n",
    "                    # if n == hasmap[word]:\n",
    "                    max_len = max(hasmap[word], max_len)\n",
    "        \n",
    "        arr = []\n",
    "        for word in hasmap:\n",
    "            if hasmap[word] == max_len:\n",
    "                arr.append(word)\n",
    "        return sorted(arr)[0] if len(arr) > 0 else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestWord(self, words: List[str]) -> str:\r\n",
    "        words.sort()\r\n",
    "        s = set([''])\r\n",
    "        ans = ''\r\n",
    "        for v in words:\r\n",
    "            n = len(v)\r\n",
    "            if v[:n - 1] in s:\r\n",
    "                if n > len(ans):\r\n",
    "                    ans = v\r\n",
    "                s.add(v)\r\n",
    "        return(ans)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words.sort()\n",
    "        record, res = set(),\"\"\n",
    "        for word in words:\n",
    "            if word[:-1] in record or word[:-1] == \"\":\n",
    "                if len(word) > len(res): res = word\n",
    "                record.add(word)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words.sort(key=lambda x: (-len(x), x), reverse=True)\n",
    "        longest = \"\"\n",
    "        candidates = {\"\"}\n",
    "        for word in words:\n",
    "            if word[:-1] in candidates:\n",
    "                longest = word\n",
    "                candidates.add(word)\n",
    "        return longest\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        if not words:\n",
    "            return \"\"\n",
    "        res = \"\"\n",
    "\n",
    "        h_set = set(words)\n",
    "        for word in words:\n",
    "            if len(word)>len(res) or (len(word) == len(res) and word < res):\n",
    "                for i in range(1,len(word)+1):\n",
    "                    if word[:i] not in h_set:\n",
    "                        break\n",
    "                else:\n",
    "                    res = word\n",
    "        \n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        if not words:\n",
    "            return \"\"\n",
    "        res = \"\"\n",
    "\n",
    "        h_set = set(words)\n",
    "        for word in words:\n",
    "            if len(word)>len(res) or (len(word) == len(res) and word < res):\n",
    "                for i in range(1,len(word)+1):\n",
    "                    if word[:i] not in h_set:\n",
    "                        break\n",
    "                else:\n",
    "                    res = word\n",
    "        \n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        # 首先按照单词的长度升序排序，如果单词的长度相同则按照字典序降序排序\n",
    "        words.sort(key=lambda x: (-len(x), x), reverse=True)\n",
    "        res = ''\n",
    "        prefix = {''}\n",
    "        for word in words:\n",
    "            if word[:-1] in prefix:\n",
    "                res = word\n",
    "                prefix.add(word)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        if not words:\n",
    "            return \"\"\n",
    "        res = \"\"\n",
    "        a = set(words)\n",
    "        for i in words:\n",
    "            if len(i) > len(res) or (len(i)==len(res) and i < res):\n",
    "                for x in range(1,len(i)):\n",
    "                    if i[:x] not in a:\n",
    "                        break\n",
    "                else:\n",
    "                    res = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words.sort(key=lambda x: len(x))\n",
    "        hasmap = {}\n",
    "        max_len = 1\n",
    "        for word in words:\n",
    "            n = len(word)\n",
    "            if n == 1:\n",
    "                hasmap[word] = 1\n",
    "            elif word[:n-1] in hasmap:\n",
    "                hasmap[word] = hasmap[word[:n-1]] + 1\n",
    "                max_len = max(hasmap[word], max_len)\n",
    "        \n",
    "        arr = []\n",
    "        for word in hasmap:\n",
    "            if hasmap[word] == max_len:\n",
    "                arr.append(word)\n",
    "        return sorted(arr)[0] if len(arr) > 0 else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words.sort(key=lambda x:(-len(x),x),reverse=True)\n",
    "        longest = \"\"\n",
    "        candidates = {\"\"}\n",
    "        for word in words:\n",
    "            if word[:-1] in candidates:\n",
    "                longest = word\n",
    "                candidates.add(word)\n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.word = ''\n",
    "\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        tree = {}\n",
    "        words.sort(key=lambda x: len(x))\n",
    "        for w in words:\n",
    "            level = tree\n",
    "            cnt = 0\n",
    "            c = 0\n",
    "            for c in range(len(w)):\n",
    "                next_level = level.get(w[c], None)\n",
    "                if next_level is None:\n",
    "                    if c == len(w) - 1:\n",
    "                        level[w[c]] = {}\n",
    "                    break\n",
    "                level = next_level\n",
    "                cnt += 1\n",
    "            if c == len(w) - 1:\n",
    "                if len(w) > len(self.word):\n",
    "                    self.word = w\n",
    "                elif len(w) == len(self.word) and w < self.word:\n",
    "                    self.word = w\n",
    "        return self.word"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words.sort(key=lambda x:(-len(x),x),reverse=True)\n",
    "        longstr=''\n",
    "        candidates={\"\"}\n",
    "        for word in words:\n",
    "            if word[:-1] in candidates:\n",
    "                longstr=word\n",
    "                candidates.add(word)\n",
    "        return longstr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        def check(str1 , words):\n",
    "            res = []\n",
    "            for i in range(1 , len(str1)):\n",
    "                res.append(str1[0:i])\n",
    "            for j in res:\n",
    "                if j not in words:\n",
    "                    return False\n",
    "            return True\n",
    "        list1 = []\n",
    "        for i in words:\n",
    "            if check(i , words):\n",
    "                list1.append(i)\n",
    "        if not list1:\n",
    "            return \"\"\n",
    "        list1.sort(key = lambda x:(-len(x) , x))\n",
    "        return list1[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words_set=set(words)\n",
    "        l=len(words)\n",
    "        words.sort(key=lambda x:(-len(x),x),reverse=True)\n",
    "        longest=\"\"\n",
    "        candidates={\"\"}\n",
    "        for i in range(l):\n",
    "            if words[i][:-1] in candidates:\n",
    "                longest=words[i]\n",
    "                candidates.add(words[i])\n",
    "        #print(candidates)\n",
    "        return longest\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words.sort(key=lambda x: (-len(x), x), reverse=True)\n",
    "        longest = \"\"\n",
    "        #candidates = set() # \"w\" 去掉最后一个字母是\"\", 所以\"\"需要在set里面\n",
    "        #candidates.add(\"\")\n",
    "        # same as above\n",
    "        candidates = {\"\"}\n",
    "        for word in words:\n",
    "            if word[:-1] in candidates:\n",
    "                longest = word\n",
    "                candidates.add(word)\n",
    "        return longest\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        s = set(words)\n",
    "        p = set()\n",
    "\n",
    "        words.sort(key=len, reverse=True)\n",
    "        for word in words:\n",
    "            if word in p:\n",
    "                continue\n",
    "            for i in range(0, len(word)):\n",
    "                if (tmp:=word[:i+1]) in s:\n",
    "                    p.add(tmp)\n",
    "                else: break\n",
    "            if i == len(word) - 1:\n",
    "                p.add(word)\n",
    "        \n",
    "        res = list(p)\n",
    "        res.sort(key=lambda x:(-len(x), x))\n",
    "        # print(res)\n",
    "        return res[0] if res else ''\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        s = set(words)\n",
    "        p = set()\n",
    "\n",
    "        words.sort(key=len, reverse=True)\n",
    "        for word in words:\n",
    "            if word in p:\n",
    "                continue\n",
    "            for i in range(0, len(word)):\n",
    "                if (tmp:=word[:i+1]) in s:\n",
    "                    p.add(tmp)\n",
    "                else: break\n",
    "            if i == len(word) - 1:\n",
    "                p.add(word)\n",
    "        \n",
    "        res = list(p)\n",
    "        res.sort(key=lambda x:(-len(x), x))\n",
    "        # print(res)\n",
    "        return res[0] if res else ''\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words.sort(key=lambda x:(-len(x),x),reverse=True)\n",
    "        while len(words):\n",
    "            s=words.pop()\n",
    "            ss=s\n",
    "            ss=ss[:-1]          \n",
    "            while ss in words:\n",
    "                ss=ss[:-1]\n",
    "            if not ss:\n",
    "                return s\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words.sort(key=lambda x: x, reverse=True)\n",
    "        n = words.__len__()\n",
    "        m, mxlen = {}, 0\n",
    "        for i in range(n):\n",
    "            target = words[i]\n",
    "            prefix = target[:-1]\n",
    "            # print(\"words[i]={}, target={}, prefix={}\".format(words[i], target, prefix))\n",
    "            while prefix and prefix in words:\n",
    "                target = prefix\n",
    "                prefix = target[:-1]\n",
    "                # print(\"words[i]={}, target={}, prefix={}\".format(words[i], target, prefix))\n",
    "            if prefix == \"\":\n",
    "                key = words[i].__len__()\n",
    "                if key not in m.keys():\n",
    "                    m[key] = []\n",
    "                m[key].append(words[i])\n",
    "                mxlen = max(mxlen, key)\n",
    "        \n",
    "        if mxlen not in m.keys() or len(m[mxlen]) == 0:\n",
    "            return \"\"\n",
    "        vals = m[mxlen]\n",
    "        vals.sort(key=lambda x: x)\n",
    "        return vals[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words.sort(key=lambda x:(-len(x),x), reverse=True)\n",
    "        print(words)\n",
    "        for i, word in enumerate(words[::-1]):\n",
    "            m = len(word)\n",
    "            while m>0:\n",
    "                if word[:m] in words:\n",
    "                    m-=1\n",
    "                else:\n",
    "                    break\n",
    "            if m == 0:\n",
    "                return word\n",
    "\n",
    "        return ''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words.sort(key = lambda x:[-len(x),x])\n",
    "   \n",
    "        for char in words:\n",
    "            flag = True\n",
    "            for i in range(1, len(char)):\n",
    "                if char[:i] not in words:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag == False:\n",
    "                continue\n",
    "            else:\n",
    "                return char\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        word_set = set(words)\n",
    "        print(words)\n",
    "        words.sort(key = lambda x:[-len(x), x])\n",
    "        print(words)\n",
    "        \n",
    "        for num in words:\n",
    "            flag = True\n",
    "            for i in range(1,len(num)):\n",
    "                if num[:i] not in words:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag == False:\n",
    "                continue\n",
    "            else:\n",
    "                return num\n",
    "        return ''\n",
    "       \n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        print(words)\n",
    "        words.sort(key=lambda x: (-len(x), x),reverse = True)\n",
    "        print(words)\n",
    "        longest = \"\"\n",
    "        candidates = {\"\"}\n",
    "        for word in words:\n",
    "            if word[:-1] in candidates:\n",
    "                longest = word\n",
    "                candidates.add(word)\n",
    "        return longest\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "    \n",
    "    def searchPrefix(self, prefix: str) -> \"Trie\":\n",
    "        node = self\n",
    "        for ch in prefix:\n",
    "            ch = ord(ch) - ord(\"a\")\n",
    "            if not node.children[ch] or not node.children[ch].isEnd:\n",
    "                return None\n",
    "            node = node.children[ch]\n",
    "        return node\n",
    "    # 插入新节点\n",
    "    def insert(self, word: str) -> None:\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord(\"a\")\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "        node.isEnd = True\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        node = self.searchPrefix(word)\n",
    "        return node is not None and node.isEnd\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        # 一眼就是字典树 可惜我不会 先暴力求解\n",
    "        # 把字典序靠前的 排在后面 便于覆盖\n",
    "        t=Trie()\n",
    "        for i in words:\n",
    "            t.insert(i)\n",
    "        ans=''\n",
    "        for i in words:\n",
    "            print(t.search(i))\n",
    "            if t.search(i) and (len(i)>len(ans) or (len(i)==len(ans) and i<ans)):\n",
    "                ans=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] *26\n",
    "        self.isEnd = False\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        if not words:\n",
    "            return ''\n",
    "        root = trie()\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                c = ord(c) - ord('a')\n",
    "                if not cur.children[c]:\n",
    "                    cur.children[c] = trie()\n",
    "                cur = cur.children[c]\n",
    "            cur.isEnd = True\n",
    "        res = ''\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            if len(word) > len(res) or (len(word) == len(res) and word < res):\n",
    "                isword = True\n",
    "                for c in word:\n",
    "                    c = ord(c) - ord('a')\n",
    "                    cur = cur.children[c]\n",
    "                    if not cur or not cur.isEnd:\n",
    "                        isword = False\n",
    "                        break\n",
    "                if isword:\n",
    "                    res = word\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        # 目标：找出一个word使其满足该word由词典中其他单词逐步添加一个字母组成\n",
    "        # 如果word存在于前缀树trie，则组成word的所有node的isEnd均为True\n",
    "        class TrieNode:\n",
    "            def __init__(self):\n",
    "                self.children = [None] * 26\n",
    "                self.isEnd = False\n",
    "            \n",
    "        class Trie:\n",
    "            def __init__(self):\n",
    "                self.root = TrieNode()\n",
    "\n",
    "            def insert(self, word):\n",
    "                node = self.root\n",
    "                for ch in word:\n",
    "                    idx = ord(ch) - ord(\"a\")\n",
    "                    if node.children[idx] is None:\n",
    "                        node.children[idx] = TrieNode()\n",
    "                    node = node.children[idx]\n",
    "                node.isEnd = True\n",
    "\n",
    "            def search(self, word):\n",
    "                node = self.root\n",
    "                for ch in word:\n",
    "                    idx = ord(ch) - ord(\"a\")\n",
    "                    node = node.children[idx]\n",
    "                    if node.isEnd is False:\n",
    "                        return False\n",
    "                \n",
    "                return True\n",
    "\n",
    "        res = \"\"\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "        for word in words:\n",
    "            if trie.search(word) and len(word) >= len(res):\n",
    "                if len(word) == len(res) and word > res:\n",
    "                    continue\n",
    "                res = word\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "        node.isEnd = True\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if node.children[ch] is None or not node.children[ch].isEnd:\n",
    "                return False\n",
    "            node = node.children[ch]\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        t = Trie()\n",
    "        for word in words:\n",
    "            t.insert(word)\n",
    "\n",
    "        result = ''\n",
    "        for word in words:\n",
    "            if t.search(word) and (len(word)>len(result) or (len(word)==len(result) and word<result)):\n",
    "                result=word\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children= [None]*26\n",
    "        self.isEnd =False\n",
    "    def insert(self,word:str)->None:\n",
    "        ##插入字符串\n",
    "        #初始化根节点\n",
    "        #循环字符\n",
    "        #计算字符acii相对值\n",
    "        #判断是否有，没有就插入，并赋值新节点\n",
    "        #赋值字节点，进行下一轮循环判断\n",
    "        #遍历完后，在子节点的 isEnd中赋值True\n",
    "        node=self\n",
    "        for ch in word:\n",
    "            ch=ord(ch)-ord(\"a\")\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch]=Trie()\n",
    "            node=node.children[ch]\n",
    "        node.isEnd=True\n",
    "    \n",
    "    def search(self,word:str)->bool:\n",
    "        #查找是否有完全匹配的字符串,ps:并且word是其他单词逐步添加一个字母组成（在前缀树表现为 字符存在，且对应的子节点的isEnd 是Ture）\n",
    "        #初始化根节点\n",
    "        #遍历循环字符\n",
    "        #计算acii相对值\n",
    "        # 在前缀树中是否有\n",
    "        # 没有返回False\n",
    "        # 否则继续遍历下一个节点，直到遍历完。\n",
    "        # 看子节点 的isEnd\n",
    "        node=self\n",
    "        for ch in word:\n",
    "            ch=ord(ch)-ord(\"a\")\n",
    "            if not node.children[ch] or not node.children[ch].isEnd:\n",
    "                return False\n",
    "            node=node.children[ch]\n",
    "        return node.isEnd\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        if not words:\n",
    "            return \"\"\n",
    "        t = Trie()\n",
    "        for word in words:\n",
    "            t.insert(word)\n",
    "\n",
    "        longestWord=\"\"\n",
    "\n",
    "        for word in words:\n",
    "            for ch in word:\n",
    "                result=t.search(word)\n",
    "                if  not result:\n",
    "                    break\n",
    "\n",
    "            \n",
    "            if result and (len(word)>len(longestWord) or (len(word)==len(longestWord) and word<longestWord )):\n",
    "                longestWord=word\n",
    "        return longestWord \n",
    " \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        mt = {}  # tl = map to tuple\n",
    "        order = 0  # dictionary order\n",
    "\n",
    "        words.sort()\n",
    "        # print(words)\n",
    "        \n",
    "        for word in words:\n",
    "            if word in mt:\n",
    "                depth = mt[word][0]\n",
    "                for c in range(ord('a'), ord('z')+1):\n",
    "                    if word + chr(c) in words:\n",
    "                        mt[word + chr(c)] = (depth+1, order)\n",
    "                        order += 1\n",
    "            elif word not in mt and len(word) == 1:\n",
    "                mt[word] = (1, order)  # (depth, dictionary order)\n",
    "                order += 1\n",
    "                for c in range(ord('a'), ord('z')+1):\n",
    "                    if word + chr(c) in words:\n",
    "                        mt[word + chr(c)] = (2, order)\n",
    "                        order += 1\n",
    "            else:\n",
    "                mt[word] = (0, order)\n",
    "\n",
    "        ml = list(mt.items())\n",
    "        ml.sort(key = lambda x: (-1 * x[1][0], x[1][1]))\n",
    "        # print(ml)\n",
    "        return ml[0][0] if ml[0][1][0] > 0 else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def longestWord(self, words):\n",
    "        \"\"\"\n",
    "        :type words: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "\n",
    "        dTree={}\n",
    "        words.sort(key=lambda x:len(x))\n",
    "        for w in words:\n",
    "            tmp=dTree\n",
    "            for i in range(len(w)):\n",
    "                if w[i] in tmp:\n",
    "                    tmp=tmp[w[i]]\n",
    "                else:\n",
    "                    if i!=len(w)-1:\n",
    "                        break\n",
    "                    tmp[w[i]]={}\n",
    "                    tmp=tmp[w[i]]\n",
    "        print(dTree)\n",
    "        res=[]\n",
    "        self.dfs(dTree,res,\"\")\n",
    "        res.sort()\n",
    "        return res[0]\n",
    "                \n",
    "\n",
    "\n",
    "    def dfs(self,tree,res,tmp):\n",
    "        if len(res)==0:\n",
    "            res.append(tmp)\n",
    "        else:\n",
    "            if len(tmp)>len(res[0]):\n",
    "                res.clear()\n",
    "                res.append(tmp)\n",
    "            elif len(tmp)==len(res[0]):\n",
    "                res.append(tmp)\n",
    "        if len(tree)>0:\n",
    "            for k in tree.keys():\n",
    "                newtmp=tmp+k\n",
    "                self.dfs(tree[k],res,newtmp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        \n",
    "        words = sorted(words, key=lambda x:len(x))\n",
    "        trie = Trie()\n",
    "\n",
    "        longest = 0\n",
    "        res = []\n",
    "        for w in words:\n",
    "            if len(w) == 1:\n",
    "                trie.add(w)\n",
    "                if len(w) > longest:\n",
    "                    longest = 1\n",
    "                    res = [w]\n",
    "                elif len(w) == longest:\n",
    "                    res.append(w)\n",
    "            else:\n",
    "                if trie.search(w[:-1]):\n",
    "                    trie.add(w)\n",
    "                    if len(w) > longest:\n",
    "                        longest = len(w)\n",
    "                        res = [w]\n",
    "                    elif len(w) == longest:\n",
    "                        res.append(w)        \n",
    "        \n",
    "        return \"\" if not res else sorted(res)[0]\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = dict()\n",
    "        self.end = False\n",
    "\n",
    "    def add(self, word):\n",
    "        parent = self\n",
    "        for w in word:\n",
    "            if w not in parent.children:\n",
    "                parent.children[w] = Trie()\n",
    "            parent = parent.children[w]\n",
    "        parent.end = True\n",
    "\n",
    "    def search(self, word):\n",
    "        parent = self\n",
    "        for w in word:\n",
    "            if w not in parent.children:\n",
    "                return False\n",
    "            parent = parent.children[w]\n",
    "        return parent.end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        longest = ''\n",
    "        for word in words:\n",
    "            self.insert(word)\n",
    "\n",
    "        for word in words:\n",
    "            print('word = {}'.format(word))\n",
    "            print('搜索前longest = {}'.format(longest))\n",
    "            flag = self.search(word)\n",
    "            if flag:\n",
    "                if len(word) > len(longest):\n",
    "                    longest = word\n",
    "                    print('搜索后longest = {}'.format(longest))\n",
    "                    continue\n",
    "                if len(word) == len(longest):\n",
    "                    for idx in range(len(word)):\n",
    "                        if word[idx] > longest[idx]:\n",
    "                            print('搜索后longest = {}'.format(longest))\n",
    "                            break\n",
    "                        if word[idx] < longest[idx]:\n",
    "                            longest = word\n",
    "                            print('搜索后longest = {}'.format(longest))\n",
    "                            break\n",
    "\n",
    "        return longest\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "\n",
    "    def insert(self, word):\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if node.children[ch] is None:\n",
    "                node.children[ch] = Solution()\n",
    "            node = node.children[ch]\n",
    "        node.isEnd = True\n",
    "\n",
    "    def search_func(self, word):\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if node.children[ch] is None or not node.children[ch].isEnd:\n",
    "                return False\n",
    "            node = node.children[ch]\n",
    "        return node\n",
    "\n",
    "    def search(self, word):\n",
    "        if self.search_func(word):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    # 前缀树\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "        node.isEnd = True\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        node = self   # 从根节点出发\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if node.children[ch] is None or not node.children[ch].isEnd:   # 为空或者不是根节点\n",
    "                return False\n",
    "            node = node.children[ch]\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        t = Trie()\n",
    "        # 先把所有word都放入前缀树\n",
    "        for word in words:\n",
    "            t.insert(word)\n",
    "    \n",
    "        longest = \"\"\n",
    "        for word in words:\n",
    "            if t.search(word) and (len(word) > len(longest) or len(word) == len(longest) and word < longest):\n",
    "                longest = word\n",
    "                # 如果能找到单词且词长较大 或 词长相同但字典序较小，更新\n",
    "        return longest\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "        ans = \"\"\n",
    "        for word in words:\n",
    "            if (len(word) > len(ans) or (len(word) == len(ans) and word < ans)) and trie.search(word):\n",
    "                ans = word\n",
    "        return ans\n",
    "\n",
    "class Trie(object):\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.root = {'end':True}\n",
    "\n",
    "    def insert(self, word):\n",
    "        \"\"\"\n",
    "        Inserts a word into the trie.\n",
    "        :type word: str\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        node = self.root\n",
    "        for c in word:\n",
    "            if c not in node:\n",
    "                node[c] = {}\n",
    "            node = node[c]\n",
    "        node['end'] = True\n",
    "\n",
    "    def search(self, word):\n",
    "        \"\"\"\n",
    "        Returns if the word is in the trie.\n",
    "        :type word: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        node = self.root\n",
    "        for c in word:\n",
    "            if c not in node or 'end' not in node:\n",
    "                return False\n",
    "            node = node[c]\n",
    "        return 'end' in node\n",
    "\n",
    "\n",
    "    def startsWith(self, prefix):\n",
    "        \"\"\"\n",
    "        Returns if there is any word in the trie that starts with the given prefix.\n",
    "        :type prefix: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        node = self.root\n",
    "        for c in prefix:\n",
    "            if c not in node:\n",
    "                return False\n",
    "            node = node[c]\n",
    "        return True\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "        node.isEnd = True\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if node.children[ch] is None or not node.children[ch].isEnd:\n",
    "                return False\n",
    "            node = node.children[ch]\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        t = Trie()\n",
    "        for word in words:\n",
    "            t.insert(word)\n",
    "        longest = \"\"\n",
    "        for word in words:\n",
    "            if t.search(word) and (len(word) > len(longest) or len(word) == len(longest) and word < longest):\n",
    "                longest = word\n",
    "        return longest\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = {}\n",
    "        self.end = '#'\n",
    "    def insert(self, word):\n",
    "        node = self.root\n",
    "        for w in word:\n",
    "            if w not in node:\n",
    "                node[w] = {}\n",
    "            node = node[w]\n",
    "        node[self.end] = '#'\n",
    "    def search(self, word):\n",
    "        node = self.root\n",
    "        for w in word:\n",
    "            if w not in node:\n",
    "                return False\n",
    "            node = node[w]\n",
    "            if self.end not in node:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words.sort()\n",
    "        t = Trie()\n",
    "        max_len, res = 0, \"\"\n",
    "        for word in words:\n",
    "            t.insert(word)\n",
    "        for word in words:\n",
    "            if t.search(word):\n",
    "                if len(word) > max_len:\n",
    "                    max_len = len(word)\n",
    "                    res = word\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DictTree():\n",
    "    def __init__(self):\n",
    "        self.nodes = [None for i in range(26)]\n",
    "        self.is_trivial = False\n",
    "\n",
    "    def insert(self, s):\n",
    "        node = self\n",
    "        for ch in s:\n",
    "            n = ord(ch) - ord(\"a\")\n",
    "            if node.nodes[n] is None:\n",
    "                print(1)\n",
    "                node.nodes[n] = DictTree()\n",
    "            node = node.nodes[n]\n",
    "        node.is_trivial = True\n",
    "\n",
    "    def search(self, s):\n",
    "        node = self\n",
    "        for ch in s:\n",
    "            n = ord(ch) - ord(\"a\")\n",
    "            if node.nodes[n] is None or not node.nodes[n].is_trivial:\n",
    "                return False\n",
    "            node = node.nodes[n]\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words) -> str:\n",
    "        dt = DictTree()\n",
    "        for s in words:\n",
    "            dt.insert(s)\n",
    "\n",
    "        max_s = \"\"\n",
    "        for s in words:\n",
    "            m = dt.search(s)\n",
    "            print(f\"s: {m}\")\n",
    "            if m and (len(s) > len(max_s) or (len(s) == len(max_s) and s < max_s)):\n",
    "                max_s = s\n",
    "        return max_s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "        ans = \"\"\n",
    "        for word in words:\n",
    "            if (len(word) > len(ans) or (len(word) == len(ans) and word < ans)) and trie.search(word):\n",
    "                ans = word\n",
    "        return ans\n",
    "\n",
    "class Trie(object):\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.root = {'end':True}\n",
    "\n",
    "    def insert(self, word):\n",
    "        \"\"\"\n",
    "        Inserts a word into the trie.\n",
    "        :type word: str\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        node = self.root\n",
    "        for c in word:\n",
    "            if c not in node:\n",
    "                node[c] = {}\n",
    "            node = node[c]\n",
    "        node['end'] = True\n",
    "\n",
    "    def search(self, word):\n",
    "        \"\"\"\n",
    "        Returns if the word is in the trie.\n",
    "        :type word: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        node = self.root\n",
    "        for c in word:\n",
    "            if c not in node or 'end' not in node:\n",
    "                return False\n",
    "            node = node[c]\n",
    "        return 'end' in node\n",
    "\n",
    "\n",
    "    def startsWith(self, prefix):\n",
    "        \"\"\"\n",
    "        Returns if there is any word in the trie that starts with the given prefix.\n",
    "        :type prefix: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        node = self.root\n",
    "        for c in prefix:\n",
    "            if c not in node:\n",
    "                return False\n",
    "            node = node[c]\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words = words + [\"\"]\n",
    "        def helper(s):\n",
    "            if not s:\n",
    "                return True\n",
    "            if s[:-1] in words:\n",
    "                return helper(s[:-1])\n",
    "            return False\n",
    "        ans = \"\"\n",
    "        length = 0\n",
    "        for i in words:\n",
    "            if helper(i):\n",
    "                if len(i)>length:\n",
    "                    length = len(i)\n",
    "                    ans = i\n",
    "                elif len(i) == length:\n",
    "                    if i<ans:\n",
    "                        ans = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self) -> None:\n",
    "        self.child = dict()\n",
    "    \n",
    "    def insert(self, word: str) -> None:\n",
    "        cur = self.child\n",
    "        for ch in word:\n",
    "            if ch not in cur:\n",
    "                cur[ch] = dict()\n",
    "            cur = cur[ch]\n",
    "        cur['#'] = dict()  # '#'代表单词结束\n",
    "    \n",
    "    def search(self, word: str) -> bool:\n",
    "        cur = self.child\n",
    "        for ch in word:\n",
    "            # 这个单词不是由前面的单词逐步添加词构成的\n",
    "            if ch not in cur or '#' not in cur[ch]:\n",
    "                return False\n",
    "            cur = cur[ch]\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        trie = Trie()\n",
    "\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "        \n",
    "        ans = ''\n",
    "\n",
    "        for word in words:\n",
    "            # print(word, trie.search(word))\n",
    "            if trie.search(word) and (len(word) > len(ans) or (len(word) == len(ans) and ans > word)):\n",
    "                ans = word\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class trie:\n",
    "    def __init__(self):\n",
    "        self.child = {}\n",
    "    def insert(self,word):\n",
    "        node = self.child\n",
    "        for x in word:\n",
    "            if x not in node.keys():\n",
    "                node[x] = {}\n",
    "            node = node[x]\n",
    "        node['#'] = '#'\n",
    "    def search(self,word):\n",
    "        node = self.child\n",
    "        for x in word:\n",
    "            if x in node.keys():\n",
    "                node = node[x]\n",
    "            else:\n",
    "                return False\n",
    "        return \"#\" in node.keys()\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        def query(word,search):\n",
    "            for i in range(1, len(word) + 1):\n",
    "                if not search(word[:i]):\n",
    "                    return False\n",
    "            return True\n",
    "        tree = trie()\n",
    "        for s in words:\n",
    "            tree.insert(s)\n",
    "        ans = \"\"\n",
    "        for s in words:\n",
    "            n, m = len(s), len(ans)\n",
    "            if n < m: continue\n",
    "            if n == m and s > ans:\n",
    "                continue\n",
    "            if query(s,tree.search):\n",
    "                ans = s\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = {}\n",
    "        self.end = \"#\"\n",
    "    def insert(self,word):\n",
    "        node = self.root\n",
    "        for w in word:\n",
    "            if not w in node:\n",
    "                node[w] = {}\n",
    "            node = node[w]\n",
    "        node[self.end] = \"#\"        \n",
    "    def search(self, word):\n",
    "        node = self.root\n",
    "        for w in word:\n",
    "            if w not in node:\n",
    "                return False\n",
    "            node = node[w]\n",
    "            if self.end not in node:\n",
    "                return False\n",
    "        return True        \n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words.sort()\n",
    "        t = Trie()\n",
    "        max_len, res = 0, ''\n",
    "        for word in words:\n",
    "            t.insert(word)\n",
    "        for word in words:\n",
    "            if t.search(word):\n",
    "                if len(word) > max_len:\n",
    "                    max_len = len(word)\n",
    "                    res = word\n",
    "        return res                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "        ans = ''\n",
    "        for word in words:\n",
    "            if (len(word)>len(ans) or (len(word)==len(ans) and word < ans)) and trie.search(word):\n",
    "                ans = word\n",
    "        return ans\n",
    "\n",
    "class Trie(object):\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.root = {'end':True}\n",
    "\n",
    "    def insert(self, word):\n",
    "        \"\"\"\n",
    "        Inserts a word into the trie.\n",
    "        :type word: str\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        node = self.root\n",
    "        for c in word:\n",
    "            if c not in node:\n",
    "                node[c] = {}\n",
    "            node = node[c]\n",
    "        node['end'] = True\n",
    "\n",
    "    def search(self, word):\n",
    "        \"\"\"\n",
    "        Returns if the word is in the trie.\n",
    "        :type word: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        node = self.root\n",
    "        for c in word:\n",
    "            if c not in node or 'end' not in node:\n",
    "                return False\n",
    "            node = node[c]\n",
    "        return 'end' in node\n",
    "\n",
    "\n",
    "    def startsWith(self, prefix):\n",
    "        \"\"\"\n",
    "        Returns if there is any word in the trie that starts with the given prefix.\n",
    "        :type prefix: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        node = self.root\n",
    "        for c in prefix:\n",
    "            if c not in node:\n",
    "                return False\n",
    "            node = node[c]\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        if len(words) == 1:\n",
    "            return words[0]\n",
    "\n",
    "        words.sort()\n",
    "        d = collections.defaultdict(list)\n",
    "        max_len = 0\n",
    "        for i in words:\n",
    "            max_len = max(len(i), max_len)\n",
    "            d[len(i)].append(i)\n",
    "\n",
    "        # 會拆分成 由最大的開始往前找\n",
    "        # d[5] = [\"world\"]\n",
    "        # d[4] = [\"worl\"]\n",
    "        # d[3] = [\"worl\"] ...\n",
    "        # 可以遞迴，或是從小到大找\n",
    "        # 題目沒有說明由其它單詞逐步添加，那第一個單詞會是一個，或是會有>1的個數再逐步添加\n",
    "\n",
    "        duplicate = set()\n",
    "\n",
    "        def dfs(prestr, level):\n",
    "            if level in d.keys():\n",
    "                for v in d[level]:\n",
    "                    if v not in duplicate and v.startswith(prestr):\n",
    "                        duplicate.add(v)\n",
    "                        ans.append(v)\n",
    "                        dfs(v, level + 1)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        for v in d[1]:\n",
    "            ans.append(v)\n",
    "            dfs(v, len(v) + 1)\n",
    "            \n",
    "        max_len = 0\n",
    "        d.clear()\n",
    "        for i in ans:\n",
    "            max_len = max(len(i), max_len)\n",
    "            d[len(i)].append(i)\n",
    "\n",
    "        if len(d) == 0:\n",
    "            return \"\"\n",
    "        return sorted(d[max_len])[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        f = {}\n",
    "\n",
    "        def addWord(word: str):\n",
    "            tmp = f\n",
    "            for w in word:\n",
    "                if w not in tmp:\n",
    "                    tmp[w] = {}\n",
    "                tmp = tmp[w]\n",
    "            tmp[\"end\"] = True\n",
    "\n",
    "        for word in words:\n",
    "            addWord(word)\n",
    "\n",
    "        ans = ''\n",
    "        cur = ''\n",
    "\n",
    "        def dfs(f):\n",
    "            nonlocal cur, ans\n",
    "            for alpha in f:\n",
    "                if alpha != \"end\" and \"end\" in f[alpha]:\n",
    "                    cur += alpha\n",
    "                    dfs(f[alpha])\n",
    "                    cur = cur[:-1]\n",
    "                else:\n",
    "                    if len(cur) == len(ans):ans = min(cur, ans)\n",
    "                    if len(cur) > len(ans):ans = cur\n",
    "\n",
    "        dfs(f)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        trie = Trie()\n",
    "        trie.insert(words=words)\n",
    "        maxLength = 0\n",
    "        maxStr = []\n",
    "        def helper(current, tmpStr):\n",
    "            nonlocal maxLength, maxStr\n",
    "            if len(tmpStr) > maxLength:\n",
    "                maxLength = len(tmpStr)\n",
    "                maxStr = [tmpStr]\n",
    "\n",
    "            if len(tmpStr) == maxLength:\n",
    "                maxStr.append(tmpStr)\n",
    "\n",
    "            for c in current:\n",
    "                if '#' in current[c]:\n",
    "                    helper(current[c], tmpStr+c)\n",
    "\n",
    "        helper(trie.lookup, '')\n",
    "        if maxLength == 0:\n",
    "            return ''\n",
    "        maxStr.sort()\n",
    "        return maxStr[0]\n",
    "\n",
    "class Trie(object):\n",
    "    def __init__(self):\n",
    "        self.lookup = dict()\n",
    "\n",
    "    def insert(self, words):\n",
    "\n",
    "        for word in words:\n",
    "            current = self.lookup\n",
    "            for c in word:\n",
    "                if c not in current:\n",
    "                    current[c] = dict()\n",
    "                current = current[c]\n",
    "            current['#'] = '$'\n",
    "\n",
    "print(Solution().longestWord(words = [\"w\",\"wo\"]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = dict()\n",
    "        self.is_end = False\n",
    "\n",
    "    def insert(self, word):\n",
    "        cur = self\n",
    "        for c in word:\n",
    "            if c not in cur.children:\n",
    "                cur.children[c] = Trie()\n",
    "            cur = cur.children[c]\n",
    "        cur.is_end = True\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        trie = Trie()\n",
    "        for w in words:\n",
    "            trie.insert(w)\n",
    "        res, path = '', ''\n",
    "        def backtrack(path, node):\n",
    "            nonlocal res\n",
    "            if len(path) > len(res) or (len(path) == len(res) and path < res):\n",
    "                res = path\n",
    "            for k, v in node.children.items():\n",
    "                if v.is_end:\n",
    "                    backtrack(path + k, v)\n",
    "        backtrack(path, trie)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = {}\n",
    "        self.end = '#'\n",
    "    def insert(self, word):\n",
    "        node = self.root\n",
    "        for w in word:\n",
    "            if w not in node:\n",
    "                node[w] = {}\n",
    "            node = node[w]\n",
    "        node[self.end] = '#'\n",
    "    def search(self, word):\n",
    "        node = self.root\n",
    "        for w in word:\n",
    "            if w not in node:\n",
    "                return False\n",
    "            node = node[w]\n",
    "            if self.end not in node:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        words.sort()\n",
    "        t = Trie()\n",
    "        max_len, res = 0, ''\n",
    "        for word in words:\n",
    "            t.insert(word)\n",
    "        for word in words:\n",
    "            if t.search(word):\n",
    "                if len(word) > max_len:\n",
    "                    max_len = len(word)\n",
    "                    res = word\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "        ans = \"\"\n",
    "        for word in words:\n",
    "            if (len(word) > len(ans) or (len(word) == len(ans) and word < ans)) and trie.search(word):\n",
    "                ans = word\n",
    "        return ans\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.dic = {'end':True}\n",
    "\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        \"\"\"\n",
    "        Inserts a word into the trie.\n",
    "        \"\"\"\n",
    "        t = self.dic\n",
    "        for w in word:\n",
    "            if w not in t:\n",
    "                t[w] = {}\n",
    "            t = t[w]\n",
    "        t['end'] = True\n",
    "\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        \"\"\"\n",
    "        Returns if the word is in the trie.\n",
    "        \"\"\"\n",
    "        t = self.dic\n",
    "        for w in word:\n",
    "            if w not in t or 'end' not in t:\n",
    "                return False\n",
    "            t = t[w]\n",
    "        return 'end' in t\n",
    "\n",
    "\n",
    "    def startsWith(self, prefix: str) -> bool:\n",
    "        \"\"\"\n",
    "        Returns if there is any word in the trie that starts with the given prefix.\n",
    "        \"\"\"\n",
    "        t = self.dic\n",
    "        for w in prefix:\n",
    "            if w not in t:\n",
    "                return False\n",
    "            t = t[w]\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        trie = Trie()\n",
    "        trie.insert(words=words)\n",
    "        maxLength = 0\n",
    "        maxStr = []\n",
    "        def helper(current, tmpStr):\n",
    "            nonlocal maxLength, maxStr\n",
    "            if len(tmpStr) > maxLength:\n",
    "                maxLength = len(tmpStr)\n",
    "                maxStr = [tmpStr]\n",
    "\n",
    "            if len(tmpStr) == maxLength:\n",
    "                maxStr.append(tmpStr)\n",
    "\n",
    "            for c in current:\n",
    "                if '#' in current[c]:\n",
    "                    helper(current[c], tmpStr+c)\n",
    "\n",
    "        helper(trie.lookup, '')\n",
    "        if maxLength == 0:\n",
    "            return ''\n",
    "        maxStr.sort()\n",
    "        return maxStr[0]\n",
    "\n",
    "class Trie(object):\n",
    "    def __init__(self):\n",
    "        self.lookup = dict()\n",
    "\n",
    "    def insert(self, words):\n",
    "\n",
    "        for word in words:\n",
    "            current = self.lookup\n",
    "            for c in word:\n",
    "                if c not in current:\n",
    "                    current[c] = dict()\n",
    "                current = current[c]\n",
    "            current['#'] = '$'\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str: \n",
    "        if words is None or len(words) == 0:\n",
    "            return \"\"\n",
    "        root = Trie()\n",
    "\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                if c in cur.children:\n",
    "                    cur = cur.children[c]\n",
    "                else:\n",
    "                    newNode = Trie()\n",
    "                    cur.children[c] = newNode\n",
    "                    cur = newNode\n",
    "            cur.val = words\n",
    "            cur.isEnd = True\n",
    "\n",
    "        result = \"\"\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            if len(word) > len(result) or (len(word) == len(result) and word < result):\n",
    "                isWord = True\n",
    "                for c in word:\n",
    "                    cur = cur.children[c]\n",
    "                    if not cur.isEnd:\n",
    "                        isWord = False\n",
    "                        break\n",
    "                result = word if isWord else result\n",
    "        return result\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.isEnd = False\n",
    "        self.val = \"\"\n",
    "\n",
    "\n",
    "            \n",
    "# 每个都有终止符"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.d = {}\n",
    "    \n",
    "    def insert(self, word):\n",
    "        t = self.d\n",
    "        for w in word:\n",
    "            if w not in t:\n",
    "                t[w] = {}\n",
    "            t = t[w]\n",
    "        t['end'] = word\n",
    "\n",
    "    def search(self, s):\n",
    "        t = self.d\n",
    "        # print('t =', t)\n",
    "        for w in s:\n",
    "            if w not in t or 'end' not in t[w]:\n",
    "                return False\n",
    "            t = t[w]\n",
    "        return True\n",
    "\n",
    "    # def __init__(self):\n",
    "    #     self.children = [None] * 26\n",
    "    #     self.isEnd = False\n",
    "\n",
    "    # def insert(self, word: str) -> None:\n",
    "    #     node = self\n",
    "    #     for ch in word:\n",
    "    #         ch = ord(ch) - ord('a')\n",
    "    #         if not node.children[ch]:\n",
    "    #             node.children[ch] = Trie()\n",
    "    #         node = node.children[ch]\n",
    "    #     node.isEnd = True\n",
    "\n",
    "    # def search(self, word: str) -> bool:\n",
    "    #     node = self\n",
    "    #     for ch in word:\n",
    "    #         ch = ord(ch) - ord('a')\n",
    "    #         if node.children[ch] is None or not node.children[ch].isEnd:\n",
    "    #             return False\n",
    "    #         node = node.children[ch]\n",
    "    #     return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "        # print(trie.d)\n",
    "        ans = ''\n",
    "        for word in words:\n",
    "            # print(trie.search(word), word)\n",
    "            if trie.search(word) and (len(word)>len(ans) or len(word)==len(ans) and word<ans):\n",
    "                ans = word\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.child = {}\n",
    "        self.isend = None \n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "    \n",
    "    def insert(self,word):\n",
    "        cur = self.root\n",
    "        for c in word:\n",
    "            if c not in cur.child:\n",
    "                cur.child[c] = TrieNode()\n",
    "            cur = cur.child[c]\n",
    "        cur.isend = word \n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        tire = Trie()\n",
    "        # 插入前缀树，字典树\n",
    "        for word in words:\n",
    "            tire.insert(word)\n",
    "        # 在字典树上面进行BFS搜索\n",
    "        res = ''\n",
    "        q = deque()\n",
    "        q.append(tire.root)\n",
    "        step = -1 \n",
    "        max_depth = 0\n",
    "        while q:\n",
    "            step += 1\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if step > max_depth:\n",
    "                    max_depth = step \n",
    "                    res = node.isend\n",
    "                for nxt in sorted(node.child.keys()):\n",
    "                    if node.child[nxt].isend:\n",
    "                        q.append(node.child[nxt])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class  Solution:\n",
    "    #  Trie\n",
    "    #  N  is  the  size  of  words,  M  is  the  size  of  each  word  in  words\n",
    "    #  Time  Complexity:0(sigma(M*N))\n",
    "    #  Space  Complexity:  0(sigma(M*N))\n",
    "    def  longestWord(self,words:List[str])  ->  str:\n",
    "        if words is None or len(words)  ==  0:\n",
    "            return  \"\"\n",
    "        root = Trie()\n",
    "        #  Insert  each  word  into  trie\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                if c in cur.children:\n",
    "                    cur = cur.children[c]\n",
    "                else:\n",
    "                    newNode = Trie(  )\n",
    "                    cur.children[c] = newNode\n",
    "                    cur = newNode\n",
    "            cur.val = word\n",
    "            cur.isEnd  =  True\n",
    "        #  Looking  for  the  eligible  word\n",
    "        result  =  \"\"\n",
    "        for  word  in  words:\n",
    "            cur  =  root\n",
    "            if  len(word)>len(result) or (len(word)==len(result) and word<result):\n",
    "                isWord = True\n",
    "                for c in word:\n",
    "                    cur = cur.children[c]\n",
    "                    if not cur.isEnd:\n",
    "                        isWord = False\n",
    "                        break\n",
    "                result  =  word if isWord else result\n",
    "        return result\n",
    "class Trie:\n",
    "    def  __init__(self):\n",
    "        self.children  =  {}\n",
    "        self.isEnd  =  False\n",
    "        self.val  =  \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    __slots__ = 'ch', 'children', 'is_word'\n",
    "    def __init__(self, ch='', is_word=False):\n",
    "        self.ch = ch\n",
    "        self.children = dict()\n",
    "        self.is_word = is_word\n",
    "\n",
    "def insert(root, word):\n",
    "    node = root\n",
    "    for c in word:\n",
    "        if c not in node.children:\n",
    "            node.children[c] = TrieNode(c)\n",
    "        node = node.children[c]\n",
    "    node.is_word = True\n",
    "\n",
    "def dfs(node):\n",
    "    if not node.is_word:\n",
    "        return ''\n",
    "    res = ''\n",
    "    for c in sorted(node.children.keys()):\n",
    "        ret = dfs(node.children[c])\n",
    "        if len(ret) > len(res):\n",
    "            res = ret\n",
    "        elif len(ret) == len(res):\n",
    "            res = min(res, ret)\n",
    "    return node.ch + res\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        root = TrieNode(is_word=True)\n",
    "        for w in words:\n",
    "            insert(root, w)\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode():\n",
    "    def __init__(self):\n",
    "        self.children = defaultdict(TrieNode)\n",
    "        self.isword = False\n",
    "\n",
    "\n",
    "class Trie():\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def insert(self, word):\n",
    "        cur = self.root\n",
    "        for w in word:\n",
    "            cur = cur.children[w]\n",
    "        cur.isword = True\n",
    "\n",
    "    def search(self, word):\n",
    "        cur = self.root\n",
    "        for w in word:\n",
    "            cur = cur.children.get(w)\n",
    "            if cur is None:\n",
    "                return False\n",
    "        return cur.isword\n",
    "\n",
    "    def startsWith(self, prefix: str) -> bool:\n",
    "        cur = self.root\n",
    "        for w in prefix:\n",
    "            cur = cur.children.get(w)\n",
    "            if cur is None:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        trie = Trie()\n",
    "        max_length = 0\n",
    "        res = ''\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "        for word in words:\n",
    "            cur = trie.root\n",
    "            if (len(word) > len(res)) or (len(word) == len(res) and word < res):\n",
    "                is_res = True\n",
    "                for w in word:\n",
    "                    cur = cur.children.get(w)\n",
    "                    if not cur.isword:\n",
    "                        is_res = False\n",
    "                        break\n",
    "                if is_res:\n",
    "                    res = word\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.isEnd = False\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "    \n",
    "    def insert(self, word):\n",
    "        node = self.root\n",
    "        for char in word:\n",
    "            if char not in node.children:\n",
    "                node.children[char] = TrieNode()\n",
    "            node = node.children[char]\n",
    "        node.isEnd = True\n",
    "    \n",
    "    def search(self, word):\n",
    "        node = self.root\n",
    "        for char in word:\n",
    "            #   not node.children[char].isEnd \n",
    "            # 题目要求必须返回 其他单词逐步添加一个字母组成\n",
    "            # 如果一个单词不是由其他单词逐步添加而成 那么该单词的所有前缀单词的结束休止符必然为False\n",
    "            if char not in node.children or not node.children[char].isEnd:\n",
    "                return False\n",
    "            node = node.children[char]\n",
    "        return node.isEnd\n",
    "    \n",
    "    def startsWith(self, profix):\n",
    "        node = self.root\n",
    "        for char in profix:\n",
    "            if char not in node.children:\n",
    "                return False\n",
    "            node = node.children[char]\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "\n",
    "        t = Trie()\n",
    "        for word in words:\n",
    "            t.insert(word)\n",
    "        \n",
    "        longest = \"\"\n",
    "        for word in words:\n",
    "            if t.search(word) and (len(word) > len(longest) or len(word) == len(longest) and word < longest):\n",
    "                #len(word) == len(longest) and word < longest:\n",
    "                # 两个单词个数相等的情况下，返回字典序小的那个\n",
    "                longest = word\n",
    "        return longest\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.isEnd = False\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "    \n",
    "    def insert(self, word):\n",
    "        node = self.root\n",
    "        for char in word:\n",
    "            if char not in node.children:\n",
    "                node.children[char] = TrieNode()\n",
    "            node = node.children[char]\n",
    "        node.isEnd = True\n",
    "    \n",
    "    def search(self, word):\n",
    "        node = self.root\n",
    "        for char in word:\n",
    "            if char not in node.children or not node.children[char].isEnd:\n",
    "                return False\n",
    "            node = node.children[char]\n",
    "        return node.isEnd\n",
    "    \n",
    "    def startsWith(self, profix):\n",
    "        node = self.root\n",
    "        for char in profix:\n",
    "            if char not in node.children:\n",
    "                return False\n",
    "            node = node.children[char]\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "\n",
    "        t = Trie()\n",
    "        for word in words:\n",
    "            t.insert(word)\n",
    "        \n",
    "        longest = \"\"\n",
    "        for word in words:\n",
    "            if t.search(word) and (len(word) > len(longest) or len(word) == len(longest) and word < longest):\n",
    "                #len(word) == len(longest) and word < longest:\n",
    "                # 两个单词个数相等的情况下，返回字典序小的那个\n",
    "                longest = word\n",
    "        return longest\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.is_end = False\n",
    "        self.childs = {}\n",
    "    \n",
    "    def insert(self, word):\n",
    "        node = self\n",
    "        for c in word:\n",
    "            if c not in node.childs:\n",
    "                node.childs[c] = Trie()\n",
    "            node = node.childs[c]\n",
    "        node.is_end = True\n",
    "    \n",
    "    def search(self, word):\n",
    "        node = self\n",
    "        for c in word:\n",
    "            if c not in node.childs:\n",
    "                return False\n",
    "            node = node.childs[c]\n",
    "        return node.is_end\n",
    "    \n",
    "    def stratsWith(self, prefix):\n",
    "        node = self\n",
    "        for c in prefix:\n",
    "            if c not in prefix.childs:\n",
    "                return False\n",
    "            node = node.childs[c]\n",
    "        return True\n",
    "    \n",
    "    def each_is_word(self, word):\n",
    "        node = self\n",
    "        for c in word:\n",
    "            if c not in node.childs:\n",
    "                return False\n",
    "            node = node.childs[c]\n",
    "            if not node.is_end:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        trie = self.build_trie(words)\n",
    "\n",
    "        select_word = \"\"\n",
    "        for word in words:\n",
    "            if trie.each_is_word(word):\n",
    "                if len(word) > len(select_word) or (len(word) == len(select_word) and word < select_word):\n",
    "                    select_word = word\n",
    "        return select_word\n",
    "    \n",
    "    def build_trie(self, words):\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "        return trie\n",
    "\n",
    "solution = Solution()\n",
    "words = [\"w\",\"wo\",\"wor\",\"worl\", \"world\"]\n",
    "print(solution.longestWord(words))\n",
    "# words = [\"a\", \"banana\", \"app\", \"appl\", \"ap\", \"apply\", \"apple\"]\n",
    "# print(solution.longestWord(words))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class  Solution:\n",
    "    #  Trie\n",
    "    #  N  is  the  size  of  words,  M  is  the  size  of  each  word  in  words\n",
    "    #  Time  Complexity:0(sigma(M*N))\n",
    "    #  Space  Complexity:  0(sigma(M*N))\n",
    "    def  longestWord(self,words:List[str])  ->  str:\n",
    "        if words is None or len(words)  ==  0:\n",
    "            return  \"\"\n",
    "        root = Trie()\n",
    "        #  Insert  each  word  into  trie\n",
    "        for word in words:\n",
    "            cur = root\n",
    "            for c in word:\n",
    "                if c in cur.children:\n",
    "                    cur = cur.children[c]\n",
    "                else:\n",
    "                    newNode = Trie(  )\n",
    "                    cur.children[c] = newNode\n",
    "                    cur = newNode\n",
    "            cur.val = word\n",
    "            cur.isEnd  =  True\n",
    "        #  Looking  for  the  eligible  word\n",
    "        result  =  \"\"\n",
    "        for  word  in  words:\n",
    "            cur  =  root\n",
    "            if  len(word)>len(result) or (len(word)==len(result) and word<result):\n",
    "                isWord = True\n",
    "                for c in word:\n",
    "                    cur = cur.children[c]\n",
    "                    if not cur.isEnd:\n",
    "                        isWord = False\n",
    "                        break\n",
    "                result  =  word if isWord else result\n",
    "        return result\n",
    "class Trie:\n",
    "    def  __init__(self):\n",
    "        self.children  =  {}\n",
    "        self.isEnd  =  False\n",
    "        self.val  =  \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode: # has children and endOfWord\n",
    "    def __init__(self):\n",
    "        self.children = {} # can be 26 for English letters\n",
    "        self.endOfWord = False # check if word ends with a letter\n",
    "\n",
    "class Trie: # a tree like data structure to solve prefix problems in string\n",
    "    def __init__(self): # init the node\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def insert(self, word: str) -> None: # insert a word inside a Trie\n",
    "        cur = self.root\n",
    "        for c in word:\n",
    "            if c not in cur.children:\n",
    "                cur.children[c] = TrieNode()\n",
    "            cur = cur.children[c]\n",
    "        cur.endOfWord = True\n",
    "\n",
    "    def search(self, word: str) -> bool: # check if a word inside trie\n",
    "        cur = self.root\n",
    "        for c in word:\n",
    "            if c not in cur.children:\n",
    "                return False\n",
    "            cur = cur.children[c]\n",
    "            if cur.endOfWord == False:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        t = Trie()\n",
    "        for word in words:\n",
    "            t.insert(word)\n",
    "\n",
    "        res = []\n",
    "        for w in words:\n",
    "            if t.search(w):\n",
    "                res.append(w)\n",
    "        if not res:\n",
    "            return ''\n",
    "        L = max(len(w) for w in res)\n",
    "        res = sorted([w for w in res if len(w) == L])\n",
    "        return res[0]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.isend = False\n",
    "        self.children= dict()\n",
    "    def insert(self, word: str) -> None:\n",
    "        cur=self\n",
    "        for i in word:\n",
    "            if i not in cur.children:\n",
    "                cur.children[i] = Trie() #每一个节点都相当于是Tire\n",
    "            cur=cur.children[i] #沿着继续插入\n",
    "        cur.isend=True\n",
    "    def search(self, word: str) -> bool:\n",
    "        cur=self #指向开头\n",
    "        for w in word:\n",
    "            if w not in cur.children or not cur.children[w].isend:\n",
    "                return False\n",
    "            cur=cur.children[w] #沿着继续寻找\n",
    "        return cur.isend==True\n",
    "    def startsWith(self, prefix: str) -> bool: #判断是否有以prefix开头的单词\n",
    "        cur=self\n",
    "        for w in prefix:\n",
    "            if w not in cur.children:\n",
    "                return False\n",
    "            cur=cur.children[w]\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        trie=Trie()\n",
    "        for i in range(len(words)):\n",
    "            trie.insert(words[i])\n",
    "        ans=\"\"\n",
    "        for i in range(len(words)):\n",
    "            if trie.search(words[i]) and (len(words[i])>len(ans) or (len(words[i])==len(ans) and words[i]<ans)):\n",
    "                ans=words[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        t = Trie()\n",
    "        longest = ''\n",
    "\n",
    "        for word in words:\n",
    "            t.insert(word)\n",
    "        \n",
    "        for word in words:\n",
    "            if t.search(word):\n",
    "                if len(word) > len(longest) or len(word) == len(longest) and word < longest:\n",
    "                    longest = word\n",
    "\n",
    "        return longest\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.is_end = False\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        node = self\n",
    "        for c in word:\n",
    "            c = ord(c) - ord('a')\n",
    "            if not node.children[c]:\n",
    "                node.children[c] = Trie()\n",
    "            node = node.children[c]\n",
    "        node.is_end = True\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        node = self\n",
    "        for c in word:\n",
    "            c = ord(c) - ord('a')\n",
    "            if not node.children[c].is_end:\n",
    "                return False\n",
    "            node = node.children[c]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode: # has children and endOfWord\n",
    "    def __init__(self):\n",
    "        self.children = {} # can be 26 for English letters\n",
    "        self.endOfWord = False # check if word ends with a letter\n",
    "\n",
    "class Trie: # a tree like data structure to solve prefix problems in string\n",
    "    def __init__(self): # init the node\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def insert(self, word: str) -> None: # insert a word inside a Trie\n",
    "        cur = self.root\n",
    "        for c in word:\n",
    "            if c not in cur.children:\n",
    "                cur.children[c] = TrieNode()\n",
    "            cur = cur.children[c]\n",
    "        cur.endOfWord = True\n",
    "\n",
    "    def search(self, word: str) -> bool: # check if a word inside trie\n",
    "        cur = self.root\n",
    "        for c in word:\n",
    "            if c not in cur.children:\n",
    "                return False\n",
    "            cur = cur.children[c]\n",
    "            if cur.endOfWord == False:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        t = Trie()\n",
    "        for word in words:\n",
    "            t.insert(word)\n",
    "\n",
    "        res = []\n",
    "        for w in words:\n",
    "            if t.search(w):\n",
    "                res.append(w)\n",
    "        if not res:\n",
    "            return ''\n",
    "        res.sort(key = lambda x: (-len(x), x))\n",
    "        return res[0]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.isEnd = False\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "    \n",
    "    def insert(self, word):\n",
    "        node = self.root\n",
    "        for char in word:\n",
    "            if char not in node.children:\n",
    "                node.children[char] = TrieNode()\n",
    "            node = node.children[char]\n",
    "        node.isEnd = True\n",
    "    \n",
    "    def search(self, word):\n",
    "        node = self.root\n",
    "        for char in word:\n",
    "            if char not in node.children or not node.children[char].isEnd:\n",
    "                return False\n",
    "            node = node.children[char]\n",
    "        return node.isEnd\n",
    "    \n",
    "    def startsWith(self, profix):\n",
    "        node = self.root\n",
    "        for char in profix:\n",
    "            if char not in node.children:\n",
    "                return False\n",
    "            node = node.children[char]\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "\n",
    "        t = Trie()\n",
    "        for word in words:\n",
    "            t.insert(word)\n",
    "        \n",
    "        longest = \"\"\n",
    "        for word in words:\n",
    "            if t.search(word) and (len(word) > len(longest) or len(word) == len(longest) and word < longest):\n",
    "                #len(word) == len(longest) and word < longest:\n",
    "                # 两个单词个数相等的情况下，返回字典序小的那个\n",
    "                longest = word\n",
    "        return longest\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        trie = Trie()\n",
    "        ans = \"\"\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "\n",
    "        for word in words:\n",
    "            if (len(ans) < len(word) or (len(ans) == len(word) and word < ans)) and trie.find(word):\n",
    "                ans = word\n",
    "        return ans\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.nodeList = [None] * 26\n",
    "        self.isEnd = False\n",
    "    \n",
    "    def insert(self, word):\n",
    "        cur = self\n",
    "        for ch in word:\n",
    "            c = ord(ch) - ord('a')\n",
    "            if not cur.nodeList[c]:\n",
    "                cur.nodeList[c] = Trie()\n",
    "            cur = cur.nodeList[c]\n",
    "        cur.isEnd = True\n",
    "\n",
    "    def find(self, word):\n",
    "        cur = self\n",
    "        for ch in word:\n",
    "            c = ord(ch) - ord('a')\n",
    "            if not cur.nodeList[c] or not cur.nodeList[c].isEnd:\n",
    "                return False\n",
    "            cur = cur.nodeList[c]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "    \n",
    "    def insert(self, word: str) -> None:\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "        node.isEnd = True\n",
    "    \n",
    "    def search(self, word: str) -> bool:\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if node.children[ch] is None or not node.children[ch].isEnd:\n",
    "                return False\n",
    "            node = node.children[ch]\n",
    "        return True\n",
    "        \n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        t = Trie()\n",
    "        for word in words:\n",
    "            t.insert(word)\n",
    "        longest = \"\"\n",
    "        for word in words:\n",
    "            if t.search(word) and (len(word) > len(longest) or len(word) == len(longest) and word < longest):\n",
    "                longest = word\n",
    "        return longest\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        class Trie:\n",
    "            def __init__(self):\n",
    "                self.next = [None]*26\n",
    "                self.e = 0\n",
    "                # self.p = 0\n",
    "            \n",
    "            def insert(self,words):\n",
    "                root = self\n",
    "                for i in words:\n",
    "                    idx = ord(i) - ord('a')\n",
    "                    if root.next[idx]:\n",
    "                        root = root.next[idx]\n",
    "                    else:\n",
    "                        t = Trie()\n",
    "                        root.next[idx] = t\n",
    "                        root = root.next[idx]\n",
    "                root.e += 1\n",
    "            def find(self,words):\n",
    "                root = self\n",
    "                for i in words:\n",
    "                    idx = ord(i) - ord('a')\n",
    "                    if not root.next[idx] or root.next[idx].e == 0:\n",
    "                        return False\n",
    "                    root = root.next[idx]\n",
    "                return True\n",
    "\n",
    "        root = Trie()\n",
    "        for w in words:\n",
    "            root.insert(w)\n",
    "        ans = \"\"\n",
    "        for w in words:\n",
    "            if root.find(w):\n",
    "                if ans == \"\":\n",
    "                    ans = w\n",
    "                else:\n",
    "                    if len(w) > len(ans):\n",
    "                        ans = w\n",
    "                    elif len(w) == len(ans):\n",
    "                        ans = sorted([ans,w])[0]\n",
    "        return ans\n",
    "\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "        node.isEnd = True\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if node.children[ch] is None or not node.children[ch].isEnd:\n",
    "                return False\n",
    "            node = node.children[ch]\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        t = Trie()\n",
    "        for word in words:\n",
    "            t.insert(word)\n",
    "        longest = \"\"\n",
    "        for word in words:\n",
    "            if t.search(word) and (len(word) > len(longest) or len(word) == len(longest) and word < longest):\n",
    "                longest = word\n",
    "        return longest\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children=[None]*26\n",
    "        self.isEnd=False\n",
    "\n",
    "    def insert(self,word):\n",
    "        node=self\n",
    "        for ch in word:\n",
    "            ch=ord(ch)-ord('a')\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch]=Trie()\n",
    "            node=node.children[ch]\n",
    "        node.isEnd=True\n",
    "\n",
    "    def search(self,word):\n",
    "        node=self\n",
    "        for ch in word:\n",
    "            ch=ord(ch)-ord('a')\n",
    "            if node.children[ch] is None or node.children[ch].isEnd is False:\n",
    "                return False\n",
    "            node=node.children[ch]\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        t=Trie()\n",
    "        for word in words:\n",
    "            t.insert(word)\n",
    "        longest=''\n",
    "        for word in words:\n",
    "            if t.search(word) and (len(word) > len(longest) or len(word) == len(longest) and word < longest):\n",
    "                longest = word\n",
    "        return longest\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord(\"a\")\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "        node.isEnd = True \n",
    "\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord(\"a\")\n",
    "            if node.children[ch] is None or not node.children[ch].isEnd:\n",
    "                return False\n",
    "            node = node.children[ch]\n",
    "        return True\n",
    "\n",
    "\n",
    "    def startsWith(self, prefix: str) -> bool:\n",
    "        node = self\n",
    "        for ch in prefix:\n",
    "            ch = ord(ch) - ord(\"a\")\n",
    "            if node.children[ch]:\n",
    "                node = node.children[ch]\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestWord(self, words: List[str]) -> str:\n",
    "        t = Trie()\n",
    "        for word in words:\n",
    "            t.insert(word)\n",
    "        longest = \"\"\n",
    "        for word in words:\n",
    "            if t.search(word) and (len(word) > len(longest) or len(word) == len(longest) and word < longest):\n",
    "                longest = word\n",
    "        return longest"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
